home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group96a.txt / 000147_icon-group-sender _Sat Jun 29 10:41:11 1996.msg < prev    next >
Internet Message Format  |  1996-09-05  |  1KB
  1. Received: by cheltenham.cs.arizona.edu; Mon, 1 Jul 1996 08:32:45 MST
  2. Date: Sat, 29 Jun 1996 10:41:11 +0200
  3. From: karczma@calvin.info.unicaen.fr (Jerzy Karczmarczuk)
  4. Message-Id: <9606290841.AA03532@canardo.unicaen.fr>
  5. To: icon-group@cs.arizona.edu
  6. Subject: Re: Ordered tables
  7. X-Sun-Charset: US-ASCII
  8. Errors-To: icon-group-errors@cs.arizona.edu
  9. Status: O
  10.  
  11.  
  12. > From: Hamish Lawson <H.Lawson@tees.ac.uk>
  13. > 
  14. > I'd like to be able to obtain the keys of a table in the order of their 
  15. > creation (key() produces them in random order). Is there a way to do 
  16. > this? Failing that, what is the best way to go about implementing a data 
  17. > structure in Icon that is both indexed and ordered?
  18. > 
  19. > | Hamish Lawson, School of Computing and Mathematics, 
  20.  
  21. Clinton Jeffery answered already. Hashed tables are popular for their
  22. efficiency, and overloading them with extra ordering info seems - in
  23. general - rather inefficient. So, Clint proposes a mirror list which keeps
  24. track of the creation time ordering. 
  25.  
  26. There is another possibility - store with each key not the bare item, but the
  27. pair [item, ord_index], eventually pair with the item a link to the predecessor/
  28. successor (or both) key(s). The memory overhead seems worse than in the proposal
  29. of CJ, but you can do it selectively. 
  30.  
  31. Jerzy Karczmarczuk
  32. Comp. Sci., University of Caen, France.
  33.